package com.my.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class GreedyProblems {


    public static void main(String[] args) {


        GreedyProblems problems = new GreedyProblems();
        System.out.println(problems.removeDuplicateLetters("leetcode"));
        System.out.println(problems.smallestSubsequence("leetcode"));

    }



    /**
     * @author zlx
     * @Description 1081. 不同字符的最小子序列 middle   与316. 去除重复字母 middle相同
     * 返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
     *
     *
     *
     * 示例 1：
     *
     * 输入："cdadabcc"
     * 输出："adbc"
     * 示例 2：
     *
     * 输入："abcd"
     * 输出："abcd"
     * 示例 3：
     *
     * 输入："ecbacba"
     * 输出："eacb"
     * 示例 4：
     *
     * 输入："leetcode"
     * 输出："letcod"
     *
     *
     * 提示：
     *
     * 1 <= text.length <= 1000
     * text 由小写英文字母组成
     *
     * @Date 2020-12-21
     * @Param [s]
     * @return java.lang.String
     **/
    public String smallestSubsequence(String s) {

        int n = s.length();
        int [] nums = new int[26];
        boolean [] isVisited = new boolean[26];

        for(int i = 0;i < n;i++){
            nums[s.charAt(i) - 'a'] ++;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < n;i++){

            char c = s.charAt(i);
            if(!isVisited[c - 'a']){

                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c){

                    if(nums[sb.charAt(sb.length() - 1) - 'a'] > 0){

                        isVisited[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    }else{
                        break;
                    }
                }
                isVisited[c - 'a'] = true;
                sb.append(c);

            }
            nums[c - 'a']--;
        }
        return sb.toString();

    }

    /**
     * @author zlx
     * @Description 316. 去除重复字母 middle
     * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
     *
     * 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "bcabc"
     * 输出："abc"
     * 示例 2：
     *
     * 输入：s = "cbacdcbc"
     * 输出："acdb"
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 104
     * s 由小写英文字母组成
     *
     * 解题思路： 基于贪心 + 栈进行求解
     *
     * s[i] > s[i+1] 就不是最小的字典序， 到s[i+2]之后存在s[i], 表示s[i]可以被删除
     * @Date 2020-12-21
     * @Param [s]
     * @return java.lang.String
     **/
    public String removeDuplicateLetters(String s) {


        //记录各个字符的数量
        int [] sNums = new int[26];
        //记录字符是否被遍历
        boolean [] flag = new boolean[26];
        for(int i = 0;i < s.length();i++){
            sNums[s.charAt(i) - 'a'] ++;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if(!flag[c - 'a']) {
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c) {

                    if(sNums[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        flag[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    }else{
                        break;
                    }
                }
                flag[c - 'a'] = true;
                sb.append(c);
            }
            sNums[c - 'a'] --;
        }
        return sb.toString();
    }

    /**
     * @author zlx
     * @Description 860. 柠檬水找零
     * 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
     *
     * 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
     *
     * 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
     *
     * 注意，一开始你手头没有任何零钱。
     *
     * 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
     *
     * 示例 1：
     *
     * 输入：[5,5,5,10,20]
     * 输出：true
     * 解释：
     * 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
     * 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
     * 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
     * 由于所有客户都得到了正确的找零，所以我们输出 true。
     * 示例 2：
     *
     * 输入：[5,5,10]
     * 输出：true
     * 示例 3：
     *
     * 输入：[10,10]
     * 输出：false
     * 示例 4：
     *
     * 输入：[5,5,10,10,20]
     * 输出：false
     * 解释：
     * 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
     * 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
     * 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
     * 由于不是每位顾客都得到了正确的找零，所以答案是 false。
     *
     *
     * 提示：
     *
     * 0 <= bills.length <= 10000
     * bills[i] 不是 5 就是 10 或是 20
     *
     * 解题思路： 基于贪心求解，20有2种找法：3* 5 or 5 + 10 由于5元使用场景比10多，优先使用10+5 作为20的找钱方式；
     * @Date 2020-12-10
     * @Param [bills]
     * @return boolean
     **/
    public boolean lemonadeChange(int[] bills) {

        int five = 0, ten = 0;
        for(int bill : bills){
            if(bill == 5){
                five++;
            }else if(bill == 10){
                if(five <= 0){
                    return false;
                }else{
                    five --;
                    ten++;
                }
            }else{

                if(five > 0 && ten > 0){

                    five --;
                    ten --;
                }else{

                    if(five >= 3){
                        five -= 3;
                    }else{
                        return false;
                    }
                }
            }
        }
        return true;
    }



    /**
     * @author zlx
     * @Description 861. 翻转矩阵后的得分
     * 有一个二维矩阵 A 其中每个元素的值为 0 或 1 。
     *
     * 移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
     *
     * 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
     *
     * 返回尽可能高的分数。
     *
     *
     *
     * 示例：
     *
     * 输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
     * 输出：39
     * 解释：
     * 转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
     * 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
     *
     *
     * 提示：
     *
     * 1 <= A.length <= 20
     * 1 <= A[0].length <= 20
     * A[i][j] 是 0 或 1
     *
     * 解题思路： 贪心算法，翻转矩阵后得到最大值，行翻转另最高位即第一列都为1，列翻转使得每一列1的个数最大；
     *
     * @Date 2020-12-07
     * @Param [A]
     * @return int
     **/
    public int matrixScore(int[][] A) {

        if(A== null || A.length == 0 || A[0].length == 0){
            return 0;
        }
        int res = 0;
        int m = A.length, n = A[0].length;
        //先按行翻转，将第一列置成1
        for(int i = 0;i < m;i++){
            if(A[i][0] == 0){
                A[i][0] = 1;
                for(int j = 1;j < n;j++){
                    A[i][j] = 1-A[i][j];
                }
            }
        }

        res += m * (1 << (n-1));
        for(int j = 1;j < n;j++){
            //除去第一列，后面每一列1的最大个数
            int countOne = 0;
            for(int i = 0;i < m;i++){
                if(A[i][j] == 1){
                    countOne ++;
                }
            }
            if(countOne < (m-countOne)){
                countOne = m - countOne;
            }
            res += countOne * (1<< (n - j - 1));
        }

        return res;
    }
}
